package algo.A05_其他排序算法;

import util.ArrayUtil;

import java.util.Arrays;

/**
 * 给定一个无序数组arr，求出需要排序的最短子数组长度。
 * 例如：arr = [1，5，3，4，2，6，7] 返回4，因为只有[5，3，4，2]需要排序。
 * 要求：O(N)
 */
public class T02_需要排序的子数组 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 0, 20);
        ArrayUtil.print(arr);
        int[] result = solution(arr);
        System.out.println("result = " + Arrays.toString(result));
    }

    /**
     * 第一个往下走的点肯定是起点，后面如果再出现向下的拐点，要更新max，最后一个小于max的点就是结束点
     */
    private static int[] solution(int[] arr) {
        int p1 = -1;
        int p2 = -1;
        int max = arr[0];//拐点处最大值
        for (int i = 0; i < arr.length; i++) {
            //出现拐点
            if (i < arr.length - 1 && arr[i + 1] < arr[i]) {
                //记录第一个拐点
                if (p1 == -1) {
                    p1 = i;
                }
                //当前拐点比上一个拐点的值更大时，更新max
                if (arr[i] > max) {
                    max = arr[i];
                }
            }
            //结束点p2，最后一个小于拐点的位置是结束点
            if (arr[i] < max) {
                p2 = i;
            }
        }
        //全程没有拐点
        if (p1 == -1) {
            return new int[]{0, 0};
        }
        return new int[]{p1, p2};
    }
}